/*********************************************************************************
 * Software License Agreement (BSD License)
 * Copyright (c) 2012, Carlos D. Correa (info@ngraph.org)
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of netzen nor the
 *    names of its contributors may be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *********************************************************************************/
#include "timing.h"

#include "node.h"
#include "centrality.h"

#include <utility>                   // for std::pair
#include <algorithm>                 // for std::for_each
#include <limits.h>
#include <vector>
#include <stack>
#include <queue>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/betweenness_centrality.hpp>
#include <boost/graph/bc_clustering.hpp>
//#include <boost/vector_property_map.hpp>

#include <boost/graph/overloading.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/relax.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/mpl/if.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/named_function_params.hpp>

using namespace boost;
using namespace boost::detail::graph;
  
Betweenness::Betweenness(Controller *controller):AnalysisTool("Centrality","Betweenness",controller) {
    setPropertyBool("Derivatives", false);
    setPropertyStringList("Edge Weight", "Default", "edge");
    setPropertyString("Result", this->getName());
	setPropertyBool("Edge Betweenness", true);
}

void Betweenness::compute() {
    assert(controller);
    // TO DO: set up these two via UI
    Graph *g = controller->getGraph("graph");
    bool derivs = this->getPropertyBool("Derivatives");

    string resultProp = getPropertyString("Result");
    string resultDerivs = resultProp + ".Derivative";
    string edgeBetwennessProp = resultProp + ".Edge";

    compute(g, derivs);
		controller->addDataProperty("node", resultProp,PROPERTY_FLOAT);
		g->computeNodeMinMaxFloat(resultProp);

		controller->addDataProperty("edge",edgeBetwennessProp,PROPERTY_FLOAT);
    g->computeEdgeMinMaxFloat(edgeBetwennessProp);

    if(derivs) {
        controller->addDataProperty("edge",resultDerivs, PROPERTY_FLOAT);
        g->computeEdgeMinMaxFloat(resultDerivs);
    }
}

struct EdgeAttrs { 
  unsigned int index; 
  double weight; 
}; 


typedef property<edge_weight_t, double,
property<edge_index_t, std::size_t> > EdgeProperties;

typedef adjacency_list<listS, listS, undirectedS, 
property<vertex_index_t, int>, EdgeProperties> 
GraphW;
typedef adjacency_list<listS, listS, directedS, 
property<vertex_index_t, int>, EdgeProperties> 
Digraph;

struct weighted_edge 
{
	int source, target;
	double weight;
};

template<typename GraphW>
void run_weighted_test(GraphW*, int V, weighted_edge edge_init[], int E, vector<double> &centralities, vector<double> &node_centralities);
template<typename GraphW>
void  run_unweighted_test(GraphW*, int V, weighted_edge edge_init[], int E, vector<double> &centralities);


int Betweenness::compute(Graph *graph, bool needDerivs) {
  timestamp t1 = now();
  int n = graph->numNodes();
  
  string resultProp = getPropertyString("Result");
  string resultDerivs = resultProp + ".Derivative";
  string edgeProperty = getPropertyString("Edge Weight");
	string edgeBetwennessProp = resultProp + ".Edge";

  if(listener) listener->setProgress(0);

  int numEdges = 0;

	vector<weighted_edge> tempEdges;
	
	ElementIterator *it = graph->createEdgeIterator();
	for(it->begin();it->hasMoreElements();) {
		Edge *edge = (Edge*) it->next();
		float weight = graph->getAsFloat(edge, edgeProperty);
		weighted_edge e;
		
		e.source = edge->getNode0()->getIndex();
		e.target = edge->getNode1()->getIndex();
		e.weight = weight; 
		tempEdges.push_back(e);
		numEdges++;
  }
	graph->destroyIterator(it);
	
  weighted_edge *edgesweighted = new weighted_edge[numEdges];  // New for edge betweenness
	for(int i=0;i<numEdges;i++) {
		edgesweighted[i].source = tempEdges[i].source;
		edgesweighted[i].target = tempEdges[i].target;
		edgesweighted[i].weight = tempEdges[i].weight;
		//printf("Weight Edge[%d] %d -%d = %f\n", i, edgesweighted[i].source, edgesweighted[i].target,  edgesweighted[i].weight);
	}
 
	std::vector<double> vertex_centralities(n);		
	std::vector<double> edge_centralities(numEdges);
	
	run_weighted_test((Digraph*)0, n, edgesweighted, numEdges, edge_centralities, vertex_centralities);
	
	for(int i=0;i<numEdges;i++) {
		float edgeCentrality = edge_centralities[i];
		int idx1 = edgesweighted[i].source;
		int idx2 = edgesweighted[i].target;
		graph->getEdge(idx1,idx2)->setPropertyFloat(edgeBetwennessProp, edgeCentrality);
	}
	 
	for(int i=0;i<n;i++) {
    graph->getNode(i)->setPropertyFloat(resultProp, vertex_centralities[i]);
    graph->getNode(i)->createImplicitEdges(n, graph->nodes);
  }

  timestamp t2 = now();
  if(needDerivs) {
		double *sumWeights = new double[n];
		for(int gi=0;gi<n;gi++) {
			float sum = 0;
			ElementIterator *it = graph->createEdgeIterator();
			for(it->begin();it->hasMoreElements();) {
				Edge *edge = (Edge*) it->next();
				float weight = graph->getAsFloat(edge, edgeProperty);
				sum += weight;
			}
			graph->destroyIterator(it);
			sumWeights[gi] = sum;
		}
		
		weighted_edge *edgesweightedNew = new weighted_edge[numEdges];  // New for edge betweenness
    for(int i=0;i<n;i++) {
      if(listener) listener->setProgress((float) i/(float) n);
      int numEdges = 0;
			
			std::vector<double> vertex_centralitiesNew(n);		
			std::vector<double> edge_centralitiesNew(numEdges);
			for(int k=0;k<numEdges;k++) {
				edgesweightedNew[k].source = tempEdges[i].source;
				edgesweightedNew[k].target = tempEdges[i].target;
				int src = tempEdges[i].source;
				int dst = tempEdges[i].target;
				edgesweightedNew[k].weight = (i==src || i==dst)? tempEdges[i].weight + tempEdges[i].weight/sumWeights[src]:tempEdges[i].weight;
			}
			
			run_weighted_test((Digraph*)0, n, edgesweighted, numEdges, edge_centralities, vertex_centralities);
      bool transpose = true;
      for(int j=0;j<n;j++) {
				assert(graph->getImplicitEdge(i,j));
				if(transpose) {
					graph->getImplicitEdge(i,j)->setPropertySigned(resultDerivs, vertex_centralitiesNew[j]-vertex_centralities[j]);	
					if(graph->hasEdge(i,j)) {
						graph->getEdge(i,j)->setPropertySigned(resultDerivs, vertex_centralitiesNew[j]-vertex_centralities[j]);
					}
				} else {
					graph->getImplicitEdge(j,i)->setPropertySigned(resultDerivs, vertex_centralitiesNew[j]-vertex_centralities[j]);	
					if(graph->hasEdge(j,i)) {
						graph->getEdge(j,i)->setPropertySigned(resultDerivs, vertex_centralitiesNew[j]-vertex_centralities[j]);
					}
				}
			}
		}																
		delete sumWeights;
		delete edgesweightedNew;
	}
	delete edgesweighted;
  timestamp t3 = now();
  if(listener) listener->done();
 
  printf("[BETWEENNESS] Time  %f sec\n", t2 - t1);
  printf("[BETWEENNESS DERIVS] Time  %f sec\n", t3 - t2);
  return 1;
}


/***************************************/
/*  Brandes Centrality code from Boost */
/***************************************/
// Copyright 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine


using namespace boost;

const double error_tolerance = 0.001;

// Compute centrality from a weighted graph
// Returns edge and node centralities 
template<typename GraphW>
void run_weighted_test(GraphW *, int V, weighted_edge edge_init[], int E, vector<double> &edge_centralities, vector<double> &node_centralities)
{
	GraphW g(V);
	typedef typename graph_traits<GraphW>::vertex_descriptor Vertex;
	typedef typename graph_traits<GraphW>::vertex_iterator vertex_iterator;
	typedef typename graph_traits<GraphW>::edge_descriptor Edge;
	
	std::vector<Vertex> vertices(V);
	{
		vertex_iterator v, v_end;
		int index = 0;
		for (tie(v, v_end) = boost::vertices(g); v != v_end; ++v, ++index) {
			put(vertex_index, g, *v, index);
			vertices[index] = *v;
		}
	}
	
	std::vector<Edge> edges(E);
	for (int e = 0; e < E; ++e) {
		edges[e] = add_edge(vertices[edge_init[e].source],
							vertices[edge_init[e].target], 
							g).first;
		put(edge_weight, g, edges[e], edge_init[e].weight);
		put(edge_index, g, edges[e], e);
	}
	
	std::vector<double> centrality(V);
	std::vector<double> edge_centrality2(E);
	brandes_betweenness_centrality(
								   g,
								   centrality_map(
												  make_iterator_property_map(centrality.begin(), get(vertex_index, g),
																			 double()))
								   .edge_centrality_map(
														make_iterator_property_map(edge_centrality2.begin(), 
																				   get(edge_index, g), double()))
								   .vertex_index_map(get(vertex_index, g)).weight_map(get(edge_weight, g))
								   );
	edge_centralities.clear();
	for(int i=0;i<E;i++) {
		edge_centralities.push_back(edge_centrality2[i]);
	}
	node_centralities.clear(); 
	for(int i=0;i<V;i++) {
		node_centralities.push_back(centrality[i]);
	}
	
}


template<typename GraphW>
void run_unweighted_test(GraphW*, int V, weighted_edge edge_init[], int E, vector<double> &centralities)
{
	GraphW g(V);
	typedef typename graph_traits<GraphW>::vertex_descriptor Vertex;
	typedef typename graph_traits<GraphW>::vertex_iterator vertex_iterator;
	typedef typename graph_traits<GraphW>::edge_descriptor Edge;
	
	std::vector<Vertex> vertices(V);
	{
		vertex_iterator v, v_end;
		int index = 0;
		for (tie(v, v_end) = boost::vertices(g); v != v_end; ++v, ++index) {
			put(vertex_index, g, *v, index);
			vertices[index] = *v;
		}
	}
	
	std::vector<Edge> edges(E);
	for (int e = 0; e < E; ++e) {
		edges[e] = add_edge(vertices[edge_init[e].source],
							vertices[edge_init[e].target], 
							g).first;
		put(edge_weight, g, edges[e], 1.0);
		put(edge_index, g, edges[e], e);
	}
	
	std::vector<double> centrality(V);
	std::vector<double> edge_centrality1(E);
	
	brandes_betweenness_centrality(
								   g,
								   centrality_map(
												  make_iterator_property_map(centrality.begin(), get(vertex_index, g),
																			 double()))
								   .edge_centrality_map(
														make_iterator_property_map(edge_centrality1.begin(), 
																				   get(edge_index, g), double()))
								   .vertex_index_map(get(vertex_index, g)));
	
	centralities.clear();
	for(int i=0;i<E;i++) {
		centralities.push_back(edge_centrality1[i]);
	}
	
}

